import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); //3
        System.out.println(solution.lengthOfLongestSubstring("bbbbbbb")); //1
        System.out.println(solution.lengthOfLongestSubstring("pwwkew"));  //3
        System.out.println(solution.lengthOfLongestSubstring("abba"));  //2
    }

    private static char[] arr;
    List<Fragment> center;

    public int lengthOfLongestSubstring(String s) {
        if (Objects.isNull(s) || s.length() == 0) {
            return 0;
        }

        arr = s.toCharArray();
        center = new ArrayList<>();

        Fragment fragment = new Fragment(0, arr.length - 1);
        fragment.disrupt();

        while (center.size() > 0) {
            Fragment remove = center.remove(0);
            if (!remove.disrupt()) {
                return remove.length();
            }
        }

        return 1;
    }

    private void insertCenter(Fragment in) {
        for (int i = 0; i < center.size(); i++) {
            int inLength = in.length();
            if (inLength >= center.get(i).length()) {
                center.add(i, in);
                return;
            }
        }
        center.add(in);
    }

    private class Fragment {
        private int start;
        private int end;
        private int unique;

        Fragment(int s, int e) {
            start = s;
            unique = s;
            end = e;
        }


        private int length() {
            return end - start + 1;
        }

        private boolean disrupt() {
            if (unique >= end) {
                return false;
            }

            char find = arr[unique];
            List<Integer> pointList = new ArrayList<>();
            for (int i = unique + 1; i <= end; i++) {
                if (arr[i] == find) {
                    pointList.add(i);
                }
            }

            //未找到任何
            unique++;
            if (pointList.size() == 0) {
                insertCenter(this);
                return true;
            }

            //第一点
            if ((pointList.get(0) - 1) != start) {
                Fragment fragment = new Fragment(start, pointList.get(0) - 1);
                fragment.unique = unique;
                insertCenter(fragment);
            }

            //后续点
            int begin = unique;
            for (int i = 1; i < pointList.size(); i++) {
                if ((pointList.get(i) - 1) != begin) {
                    insertCenter(new Fragment(begin, pointList.get(i) - 1));
                    begin = pointList.get(i - 1) + 1;
                }
            }

            //尾段
            if (end != begin) {
                insertCenter(new Fragment(begin, end));
            }

            return true;
        }
    }
}